DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2021.10

An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D

Authors: Pankaj K. Agarwal and Alex Steiger

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract

Let C be a set of n axis-aligned cubes of arbitrary sizes in ℝ³. Let U be their union, and let κ be the number of vertices on ∂U; κ can vary between O(1) and O(n²). We show that U can be computed in O(n log³ n + κ) time if C is in general position. The algorithm also computes the union of a set of fat boxes (i.e., boxes with bounded aspect ratio) within the same time bound. If the cubes in C are congruent or have bounded depth, the running time improves to O(n log² n), and if both conditions hold, the running time improves to O(n log n).

Cite as

Pankaj K. Agarwal and Alex Steiger. An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ICALP.2021.10,
  author =	{Agarwal, Pankaj K. and Steiger, Alex},
  title =	{{An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.10},
  URN =		{urn:nbn:de:0030-drops-140790},
  doi =		{10.4230/LIPIcs.ICALP.2021.10},
  annote =	{Keywords: union of cubes, fat boxes, plane-sweep}
}

Search Results

Documents authored by Steiger, Alex

An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D

Abstract

Cite as

Thanks for your feedback!

Could not send message